package com.ljy.my_study.leetcode.分割回文串;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lijunying
 * @date 2021/11/18 14:57
 */
public class TestMain {

//    给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
//
//    回文串 是正着读和反着读都一样的字符串。
//
//             
//
//    示例 1：
//
//    输入：s = "aab"
//    输出：[["a","a","b"],["aa","b"]]
//    示例 2：
//
//    输入：s = "a"
//    输出：[["a"]]
//             
//
//    提示：
//
//            1 <= s.length <= 16
//    s 仅由小写英文字母组成
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/palindrome-partitioning
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        String s="aabbaa";
        System.out.println(new TestMain().partition(s));
    }

    public List<List<String>> partition(String s) {
        List<List<String>> result=new ArrayList<>();
        dfs(s,new ArrayList<>(),result);
        return result;
    }

    private void dfs(String s,List<String> list,List<List<String>> result){
        int len=s.length();
        for(int i=0;i<len;i++){
            if(canReverse(s,0,i)){
                list.add(s.substring(0,i+1));
                if(i==len-1){
                    result.add(new ArrayList<>(list));
                }else{
                    dfs(s.substring(i+1),list,result);
                }
                list.remove(list.size()-1);
            }
        }
    }

    private boolean canReverse(String s,int left,int right){
        while(left<right){
            if(s.charAt(left)!=s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
